﻿using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Collections.Generic;

namespace Graph
{
    public class BasicGraphImpl : IBasicGraph
    {
        private IList<Vertex> vList, visitedList;
        private Queue<Vertex> queue;
        private int[,] adjMatrix;
        private int noVer;
        public BasicGraphImpl()

        {
            vList = new List<Vertex>();
            visitedList = new List<Vertex>();
            adjMatrix = new int[noVer, noVer];
            queue = new Queue<Vertex>(vList.Count);
        }

        #region IBasicGraph Members

        public void unmark()
        {
            foreach (Vertex v in vList)
            {
                v.setMark(false);
            }
        }

        public Vertex getNextUnmark(Vertex vert)
        {
            IList<Vertex> verList = GetAdjacencies(vert);
            Vertex ver = new Vertex();
            bool found = false;
            while (!found)
            {
                foreach (Vertex v in verList)
                {
                    if (v.getMark() == false)
                    {
                        ver = v;
                        found = true;
                    }
                }
            }
            return ver;
        }

        public void AddVertex(Vertex vertex)
        {
            vList.Add(vertex);
        }

        public void AddEdge(Vertex startVertex, Vertex endVertex)
        {
            startVertex.AddEdge(endVertex);
        }

        public bool ContainsVertex(Vertex ver)
        {
            bool check = false;
            foreach (Vertex v in vList)
            {
                if (v == ver)
                {
                    check = true;
                }
            }
            return check;
        }

        public void RemoveVertex(Vertex v)
        {
            vList.Remove(v);
        }

        public void RemoveEdge(Vertex startVertex, Vertex endVertex)
        {
            startVertex.RemoveEdge(endVertex);
        }

        public bool IsAdjacent(Vertex startVertex, Vertex endVertex)
        {
            bool check = false;
            IList<Vertex> verList = GetAdjacencies(startVertex);
            foreach (Vertex v in verList)
            {
                if (v == endVertex)
                {
                    check = true;
                }
            }
            return check;
        }

        public IList<Vertex> findEdge(Vertex ver)
        {
            IList<Vertex> verList = new List<Vertex>();
            foreach (Vertex v in vList)
	        {
	            if (v==ver)
                {
                    verList = v.Edges();
                }	 
	        }
            return verList;
        }

        public IList<Vertex> GetAdjacencies(Vertex vertex)
        {
            IList<Vertex> verList = new List<Vertex>();
            foreach (Vertex v in vertex.Edges())
            {
                verList.Add(v);
            }
            return verList;
        }

        //public IEnumerator<Vertex> Vertices()
        //{
        //}

        public bool IsEmpty()
        {
            bool b = false;
            if (vList.Count == 0)
            {
                b = true;
            }
            return b;
        }

        public int GetNoOfVertices()
        {
            return this.vList.Count;
        }

        public int GetNoOfEdges()
        {
            int i = 0;
            foreach (Vertex v in vList)
            {
                foreach (Vertex ver in v.Edges())
                {
                    i++;
                }
            }
            return i;
        }

        public void Clear()
        {
            foreach (Vertex v in vList)
            {
                vList.Remove(v);
            }
        }

        //public IList<Vertex> GetAllVertexesByDepthFirst(Vertex startVertex)
        //{
        //    IList<Vertex> resultList = new List<Vertex>();
        //    Stack s = new Stack();
        //    s.Push(startVertex);
        //    while (s.Count!=0)
        //    {
        //        Vertex top = (Vertex) s.Peek();
        //        if (top.getMark()==false)
        //        {
        //            top.setMark(true);
        //            resultList.Add(top);
        //            s.Pop();
        //            foreach (Vertex v in top.Edges())
        //            {
        //                s.Push(v);
        //            }
        //        }
        //        else
        //        {
        //            s.Pop();
        //        }
        //        GetAllVertexesByDepthFirst(top);
        //    }
        //    return resultList;
        //}

        public IList<Vertex> GetAllVertexesByDepthFirst(Vertex v) 
        {
            v.setMark(true);
            visitedList.Add(v);
            foreach (Vertex u in GetAdjacencies(v))
                if (!u.getMark())
                {
                    GetAllVertexesByDepthFirst(u);
                }
            return visitedList;
        }


        public IList<Vertex> GetAllVertexesByBreadthFirst(Vertex v)
        {
            Clear();
            unmark();
            v.setMark(true);
            queue.Enqueue(v);
            while (queue.Count > 0)
            {
                Vertex ver = queue.ElementAt(0);
                visitedList.Add(queue.Dequeue());
                foreach (Vertex u in GetAdjacencies(ver))
                {
                    if (!u.getMark())
                    {
                        queue.Enqueue(u);

                    }
                }  
            }

            return visitedList;
        }

        #endregion
    }
}